<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
	<META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=windows-1252">
	<TITLE></TITLE>
	<META NAME="GENERATOR" CONTENT="OpenOffice.org 1.1.0  (Win32)">
	<META NAME="CREATED" CONTENT="20040303;23010834">
	<META NAME="CHANGEDBY" CONTENT="Oluseyi Sonaiya">
	<META NAME="CHANGED" CONTENT="20040303;23052418">
</HEAD>
<BODY LANG="en-US" DIR="LTR">
<P>In this article I'm going to introduce DFAs and NFAs, and explain
the differences between them. After showing an example, I will also
present the various methods for regex recognition employing DFAs and
NFAs. 
</P>
<H3>DFA + NFA = FSM</H3>
<P>Talking about FSMs in the past two articles, I was hiding the full
picture from you, for the sake of simplicity. Now I intend to fix
that.</P>
<P>FSM, as you already know, stands for Finite State Machine. A
more scientific name for it is FA - Finite Automaton (plural
<I>automata</I>). The theory of Finite Automatons can be classified
into several categories, but the one we need for the sake of regex
recognition is the notion of <I>determinism</I>. Something is
deterministic when it involves no <I>chance</I> - everything is known
and can be prescribed and simulated beforehand. On the other hand,
nondeterminism is about chance and probabilities. It is commonly
defined as &quot;A property of a computation which may have more than
one result&quot;. <BR>Thus, the world of FSMs can be divided to two:
a deterministic FSM is called DFA (Deterministic Finite Automaton)
and a nondeterministic FSM is called NFA (Nondeterministic Finite
Automaton). 
</P>
<H3>NFA</H3>
<P>A <I>nondeterministic finite automaton</I> is a mathematical model
that consists of:</P>
<OL>
	<LI><P STYLE="margin-bottom: 0in">A set of states S 
	</P>
	<LI><P STYLE="margin-bottom: 0in">A set of input symbols A (the
	input symbol alphabet) 
	</P>
	<LI><P STYLE="margin-bottom: 0in">A transition function <I>move</I>
	that maps state-symbol pairs to sets of states 
	</P>
	<LI><P STYLE="margin-bottom: 0in">A state s0 that is the start state
		</P>
	<LI><P>A set of states F that are the final states 
	</P>
</OL>
<P>Most of this should be familiar to you from our FSM discussion in
the past articles. I will now elaborate on a few fine points (trying
to simplify and avoid mathematical implications).<BR>A NFA <I>accepts</I>
an input string <B>X</B> if and only if there is some path in the
transition graph from the start state to some accepting (final)
state, such that the edge labels along this path spell out <B>X</B>.<BR>The
definition of a NFA doesn't pose a restriction on the amount of
states resulting in some input in some state. So, given we're in some
state <B>N</B> it is completely legal (in a NFA) to transition to
several different states given the input <B>a</B>.<BR>Furthermore,
epsilon (<B>eps</B>) transitions are allowed in a
NFA. That is, there may be a transition from state to state given &quot;no
input&quot;. <BR>I know this must sound very confusing if it's the
first time you learn about NFAs, but an example I'll show a little
later should make things more understandable. 
</P>
<H3>DFA</H3>
<P>By definition, a <I>deterministic finite automaton</I> is a
special case of a NFA, in which 
</P>
<OL>
	<LI><P STYLE="margin-bottom: 0in">No state has an <B>eps</B>-transition
		</P>
	<LI><P>For each state <B>S</B> and input <B>a</B>, there is at most
	one edge labeled <B>a</B> leaving <B>S</B>. 
	</P>
</OL>
<P>You can immediately see that a DFA is a more &quot;normal&quot;
FSM. In fact the FSMs we were discussing in the previous articles are
DFAs.</P>
<H3>Recognizing regexes with DFAs and with NFAs</H3>
<P>To make this more tolerable, consider an example comparing the DFA
and the NFA for the regex <B>(a|b)*abb</B> we saw in the previous
article. Here is the DFA (exactly the one you saw last time): 
</P>
<P><IMG SRC="ababb.jpg" NAME="Graphic1" ALIGN=BOTTOM WIDTH=720 HEIGHT=540 BORDER=0><BR><BR>And
this is the NFA: 
</P>
<P><IMG SRC="4abnfa.jpg" NAME="Graphic2" ALIGN=BOTTOM WIDTH=720 HEIGHT=540 BORDER=0>
<BR>Can you see a NFA unique feature in this diagram ? Look at state
0. When the input is <B>a</B>, where can we move ? To state 0 and
state 1 - a multiple transition, something that is illegal in a DFA.
Take a minute to convince yourself that this NFA indeed accepts
<B>(a|b)*abb</B>. For instance, consider the input string <B>abababb</B>.
Recall how NFA's <I>acceptance</I> of a string is defined. So, is
there a path in the NFA graph above that &quot;spells out&quot;
<B>abababb</B> ? There indeed is. The path will stay in state 0 for
the first 4 characters, and then will move to states 1-&gt;2-&gt;3.
Consider the input string <B>baabab</B>. Is there a path that spells
out this string ? No, there isn't, as in order to reach the final
state, we must go through <B>abb</B> in the end, which the input
string lacks. 
</P>
<P>Both NFAs and DFAs are important in computer science theory and
especially in regular expressions. Here are a few points of
difference between these constructs:</P>
<UL>
	<LI><P STYLE="margin-bottom: 0in">It is simpler to build a NFA
	directly from a regex than a DFA. 
	</P>
	<LI><P STYLE="margin-bottom: 0in">NFAs are more compact that DFAs.
	You must agree that the NFA diagram is much simpler for the
	<B>(a|b)*abb</B> regex. Due to its definition, a NFA doesn't
	explicitly need many of the transitions a DFA needs. Note how
	elegantly state 0 in the NFA example above handles the <B>(a|b)*</B>
	alternation of the regex. In the DFA, the char <B>a</B> can't both
	keep the automaton in state 0 and move it to state 1, so the many
	transitions on <B>a</B> to state 1 are required from any other
	state. 
	</P>
	<LI><P STYLE="margin-bottom: 0in">The compactness also shows in
	storage requirements. For complex regexes, NFAs are often smaller
	than DFAs and hence consume less space. There are even cases when a
	DFA for some regex is exponential in size (while an NFA is always
	linear) - though this is quite rare. 
	</P>
	<LI><P STYLE="margin-bottom: 0in">NFAs can't be directly simulated
	in the sense DFA can (recall the simulation algorithm from the
	previous article). This is due to them being nondeterministic
	&quot;beings&quot;, while our computers are deterministic. They must
	be simulated using a special technique that generates a DFA from
	their states &quot;on the fly&quot;. More on this later. 
	</P>
	<LI><P>The previous leads to NFAs being less time efficient than
	DFAs. In fact, when large strings are searched for regex matches,
	DFAs will almost always be preferable. 
	</P>
</UL>
<P>There are several techniques involving DFAs and NFAs to build
recognizers from regexes: 
</P>
<UL>
	<LI><P STYLE="margin-bottom: 0in">Build a NFA from the regex.
	&quot;Simulate&quot; the NFA to recognize input. 
	</P>
	<LI><P STYLE="margin-bottom: 0in">Build a NFA from the regex.
	Convert the NFA to a DFA. Simulate the DFA to recognize input. 
	</P>
	<LI><P STYLE="margin-bottom: 0in">Build a DFA directly from the
	regex. Simulate the DFA to recognize input. 
	</P>
	<LI><P>A few hybrid methods that are too complicated for our
	discussion. 
	</P>
</UL>
<P>In the next article, I will pick one technique and explain it in
depth. After getting to know all the algorithms involved, we will be
finally ready for the real implementation of a recognizer. 
</P>
<HR>
<P>(C) Copyright by Eli Bendersky, 2003. All rights reserved. 
</P>
</BODY>
</HTML>